Problem statement: zenit17cki

Izba

Počet bodov: 35, časový limit: 1000ms

Kubík mal včera vo svojej izbe párty. Ako to chodí, po každej poriadnej párty zostanú na dlážke zvyšky jedla a pitia, občas aj iná špina. Teraz je ráno, Kubík sa rozhliada po svojej izbe a rozmýšľa, ako to čo najefektívnejšie vyčistiť.

Izbu si môžete predstaviť ako štvorčekovú mriežku rozmerov \(r \times c\). Niektoré políčka mriežky sú čisté, niektoré sú špinavé. Na jednom z políčok je posteľ a na inom políčku je sprchovací kút, obe z týchto políčok považujeme za čisté.

Kubík na začiatku sedí na posteli, teda je na políčku s posteľou. V každom kroku môže skočiť na ľubovoľné políčko v rovnakom riadku alebo stĺpci a hneď ho vyčistiť. Táto cesta musí ale spĺňať niekoľko požiadaviek:

• Každé zo špinavých políčok musí niekedy navštíviť, aby ho vyčistil.
• Chce sa vyhnúť (už) čistým políčkam, nakoľko ich nechce (opäť) zašpiniť. Počiatočné sedenie na posteli sa neráta.
• Musí striedať smery skákania. Ak teda naposledy skočil na políčko v rovnakom stĺpci, musí teraz skočiť na políčko v rovnakom riadku, a opačne.
• Svoju cestu musí zakončiť v sprche, aby sa očistil a ďalej nešíril špinu. Potom sa už bude môcť voľne pohybovať po svojej čistučkej izbe.

Pomôžte Kubíkovi naplánovať si čistenie.

Vstup

Na prvom riadku sú dve medzerou oddelené čísla: prvý rozmer izby \(r\) a druhý rozmer izby \(c\). Platí \(4 \leq r, c \leq 1\,000\).

Nasleduje \(r\) riadkov, každý z nich obsahuje \(c\) znakov. Znak na \(i\)-tom riadku a v \(j\)-tom stĺpci popisuje počiatočný stav políčka na súradniciach \((i, j)\): A pre posteľ, B pre sprchu, . pre čistú dlážku a ~ pre špinu.

Výstup

Na prvý riadok výstupu vypíšte dĺžku cesty \(d\), teda počet navštívených políčok, vrátane začiatočného políčka s posteľou a koncového políčka so sprchou.

Na nasledujúcich \(d\) riadkoch vypíšte popis cesty. Na \(i\)-tom z nich nech sú medzerou oddelené súradnice v poradí \(i\)-teho navštíveného políčka.

Ak existuje viacero riešení, môžete vypísať ľubovoľné. Ak riešenie neexistuje, vypíšte namiesto toho \(-1\).

Príklady

Input:

4 4
A..B
~.~.
.~~.
.~.~

Output:

8
1 1
2 1
2 3
3 3
3 2
4 2
4 4
1 4

Input:

4 4
A..B
....
....
....

Output:

2
1 1
1 4

Aj v prípade, že nemusíme nič čistiť, sa chceme vyhnúť čistej dlážke.

Input:

4 4
A..B
~..~
~..~
~~~~

Output:

-1

Nezabudnite na to, že po každom skoku treba zmeniť smer! Ak by sme smer meniť nemuseli, tak by sme tento prípad vedeli vyriešiť.